package leetcode_1100;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class MatrixCellsInDistanceOrder_1029 {
	class Help{
		int[] val;
		int index;
		public Help(int[]val,int index) {
			this.val = val;
			this.index = index;
		}
	}
	public int twoCitySchedCost(int[][] costs) {
		PriorityQueue<Help> A = new PriorityQueue<Help>((o1,o2)->o1.val[0]==o2.val[0]?o1.val[1]-o2.val[1]:o1.val[0]-o2.val[0]);
        PriorityQueue<Help> B = new PriorityQueue<Help>((o1,o2)->o1.val[1]==o2.val[1]?o1.val[0]-o2.val[0]:o1.val[1]-o2.val[1]);
		for(int i=0;i<costs.length;++i) {
			Help help = new Help(costs[i],i);
			A.offer(help);
			B.offer(help);
		}
        Set<Integer> visited = new HashSet<>();
        int res = 0;
        int size = costs.length/2;
        while(size > 0) {
        	--size;
        	while(visited.contains(A.peek().index)) A.poll();
        	while(visited.contains(B.peek().index)) B.poll();
        	Help a = A.poll();
        	Help b = B.poll();
        	if(a.index == b.index) {//同一个
        		while(visited.contains(A.peek().index)) A.poll();
            	while(visited.contains(B.peek().index)) B.poll();
        		if(A.peek().val[0]+b.val[1] < B.peek().val[1]+a.val[0]) {
        			Help c = A.poll();
        			visited.add(b.index);
        			visited.add(c.index);
        			res += b.val[1]+c.val[0];
        		}else {
        			Help c = B.poll();
        			visited.add(a.index);
        			visited.add(c.index);
        			res += c.val[1]+a.val[0];
        		}
        	}else {
        		visited.add(a.index);
        		visited.add(b.index);
        		res += a.val[0]+b.val[1];
        	}
        }
        return res;
    }
	
	public int twoCitySchedCost1(int[][] costs) {
		int res = 0;
		PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->o2-o1);
		for(int[] now:costs) {
			res += now[0];//全去A
			queue.offer(now[0]-now[1]);
		}
		int size =costs.length/2;
		while(size >0 ) {
			--size;
			res -= queue.poll();
		}
		return res;
	}

}
